This invention relates generally to communications and other systems to which users gain access by being in possession of a valid certificate of authenticity. Access to the system may be for the purpose of communicating with other users, retrieving secure information, or receiving a service. More particularly, the invention relates to public key network security technology.
Public key encryption is a method of secure communication in which each user has a public encryption key and a private encryption key, and two users can communicate knowing only each other's public keys. An encryption key is a code or number, which, when taken together with an encryption algorithm, defines a unique mathematical transformation, used to encrypt or decrypt data. A public key system may be used in such a way as to ensure secrecy of the data or message being transmitted, i.e. to ensure that the message may not be understood by an eavesdropper, as well as to ensure the authenticity of the sender of the message. The present invention is concerned both with the authenticity issue, i.e. whether a user is who he purports to be, and whether he is authorized to receive certain information, and with the protection of privacy, by assuring that messages are encrypted under the right keys.
There are various types of public key systems. Some provide only digital signatures; others provide encryption only; and still others provide neither, but authenticate by means of a series of messages. For purposes of explanation, this specification describes an encryption technique known as an RSA scheme (named after the originators: Rivest, Shamir and Adleman). It will be understood by those knowledgeable in the art of cryptography that the principles of the invention can be applied equally well to public key systems of other types.
The manner in which a public key cryptography system operates to ensure authentication is relatively simple and may be understood without reference to the mathematical transformations that are used for encryption and decryption. In sending a message, a user A encrypts it for authenticity by transforming it using his private key (known only to user A). Another user B receiving the message decrypts it using A's public key, which A had provided or which B had obtained from a public directory. In public key cryptography systems, a user's public and private keys are selected such that the transformations that they effect are mutual inverses of each other. That is to say, the sequential application of both transformations will restore the message to its original form. More specifically, A's message, having been encrypted by application of A's private-key transformation, will be decrypted, by B, by application of A's public-key transformation. As noted earlier, this has nothing to do with maintaining the secrecy of the message, since anybody with knowledge of A's public key could effect the same decryption and obtain access to the original message. Encryption for secrecy of the data involves a second layer of encryption and decryption. Basically, user A encrypts for secrecy by performing a transformation using B's public key, and user B decrypts by performing a transformation using his (B's) private key. Since B's public and private keys also produce transformations that are mutual inverses, the application of B's private key to the encrypted message results in regeneration of the original message.
In summary, then, a public key system ensures authenticity because only the sender A has knowledge of the sender's private key. The message transformed by means of A's own private key is, in effect, a digital "signature" of the message by A. When the receiver B applies A's public key to the encrypted message and obtains a clear and intelligible message, this is confirmation that the message originated from user A, and not from some other user. Also, since only B has knowledge of his (B's) private key, only B can decrypt the message, and secrecy is thereby preserved.
A well known deficiency in such systems is that an imposter may easily deceive one of the parties. For example, an imposter A.sub.I may pretend to be A, telling B that A 's public key is A's public key, thereby convincing B to accept a message that purports to be from A, but is really from the imposter A.sub.I. Similarly, an imposter, B.sub.I, could contact user A and say, in effect, "I am B and here is my public key," giving A instead his (B.sub.I 's) public key. User A would then send a requested message to B.sub.I, thinking it was going to B. The imposter B.sub.I could then decrypt the message without difficulty, using his own private key.
To deal with both types of these authentication problems, many systems use authentication certificates, the basic function of which is to vouch for the relationship between a public key and the person or entity to which it belongs. In the example discussed above, a real user B would have a certificate that says, in effect, that B is the true owner of a particular public key. User A would then not be fooled into believing that imposter B.sub.I was B, since B.sub.I would not have an appropriate certificate authenticating him as the owner of B's public key. A certificate is a cryptographically signed message indicating that a trusted authority vouches for the relationship between a public key and a named principal or owner of the key. Each certificate is "signed" by the trusted authority, known as the Certification Authority, to ensure authenticity of the certificate itself. Certificates may be held by their owners, who present copies to other users with whom they wish to communicate, or may be posted in a public place. In the context of a communication network, a "public place" is any user-accessible file or record.
The certificates may also employ a public key cryptography system to produce digital signatures, but this need not necessarily be the same system as the one for which keys are being published. Basically, the use of certificates reduces the number of public keys of which a user must obtain knowledge in some manner outside the communication system. To communicate with multiple destinations, a user must obtain knowledge of a public key for each destination. But if certificates are used, the user need only acquire knowledge of one public key, that of the Certification Authority.
For complete network security, every user must have a certificate. Sometimes, however, it is necessary to invalidate certificates; for example, when an employee is fired or transferred, or when a password falls into the wrong hands. There are two common mechanisms for accomplishing this: issuing certificates with expiration dates that define relatively short validity periods, and establishing a "blacklist" of invalid certificates.
Typically, certificates have expiration dates of a year, or some shorter period, after their issue dates. Before the expiration date of his certificate, each user must apply to the Certification Authority for a new signed certificate with a new expiration date. This mechanism has the problem that if certificate expiration times are relatively short, then the overhead of reissuing certificates can be excessive. Reissuing certificates requires that the Certification Authority perform cryptographic processing for each certificate and that the renewed certificates be communicated to all parties that store them. If certificates are stored in off-line media, this can be particularly inconvenient. In some cases, such as when "smart" cards are used, certificate renewal may require a face to face meeting between the user and the Certification Authority. Any attempt to alleviate this problem, by increasing the expiration times, poses additional problems. A fired and possibly disgruntled employee may possess an unexpired certificate, giving him a period as long as several months or more in which to access the network and possibly work mischief.
This latter problem has given rise to the second mechanism for invalidating certificates, which supplements the first and is referred to as "blacklisting." The Certification Authority issues a signed "blacklist" periodically or on demand, containing a list of the certificates that have been issued in the past, but which are now to be considered invalid. Since the blacklist will normally be short, it can be issued with much greater frequency than the individual certificates. Anyone who wishes to verify that a certificate is valid must first check that the certificate has not expired, and then that the certificate is not included in a current blacklist issued by the Certification Authority. As in the case of the certificates themselves, blacklists may be presented by the certificate holders to persons with whom they wish to communicate, or may be posted in a public place. Someone verifying the authenticity of a certificate holder may in some cases require that the blacklist be a very recent one, or that a new one be obtained.
Even when blacklists are used, certificates must still have expiration dates. If they did not, the blacklists would in time grow to be so long as to be a totally impractical mechanism. As invalid certificates expire, they can be routinely removed from the blacklist, to keep the list short and manageable.
A known alternative approach used in validating certificates is to accept a certificate if it has not expired and no unexpired blacklist can be found. Another known alternative approach is to accept a certificate if it has not expired and if the latest blacklist has expired, but not "too long" ago. Both these alternatives are less secure but more robust approaches compared with simply invalidating a certificate if the only available blacklist has expired.
It will be appreciated from the foregoing, however, that, even with the use of blacklists, there are inherent difficulties, overhead and inconvenience associated with the use of authentication certificates that must be periodically renewed. The present invention provides a novel alternative approach to the ones discussed above.